Interval Methods for Zeros

We demonstrate some interval methods for zeros of functions of one or several variables.

Let us start with a simple example. Solve x^2=2.

>function f(x) &= x^2-2

                                 2
                                x  - 2

We need the derivative for the Newton algorithm.

>function df(x) &= diff(f(x),x)

2 x

We start with the interval [1,2].

>X=~1,2~

~1,2~

The Interval Newton Method is the following iteration.

Xn = X && ( m - f(m)/f(X))

It stops, if X=Xn. If X contains a zero, Xn does too. The inclusion is guaranteed, if (m-f(m)/X is a subset of X. The computation must be evaluated in interval terms, of course.

>repeat m=middle(X); Xn=X&&(~m,m~-f(~m,m~)/df(X)), until Xn==X; X=Xn; end;

~1.37,1.44~
~1.414,1.4145~
~1.414213559,1.414213566~
~1.4142135623730947,1.4142135623730954~
~1.4142135623730947,1.4142135623730954~

Since the result is a proper subset of the interior of the start interval, we have a guaranteed inclusion.

Euler implements this in the function inewton2, which takes two functions of vectors f and df, or two expressions.

>inewton(f,df,2)

~1.4142135623730947,1.4142135623730954~

The function mxminewton computes the derivative with Maxima.

>mxminewton(&f(x),~1,2~)

~1.4142135623730947,1.4142135623730954~

There is a simple function ibisect, which runs the bisection algorithm carefully to guarantee an inclusion of the solution.

>ibisect(f,1,2)

~1.414213562373094,1.414213562373096~

Example

Let us try another example.

>function f(x) &= tan(x)-x

                              tan(x) - x

We can use the bisection algorithm starting with a course interval.

>res1=bisect(&f(x),0,1,y=1e-20)

3.10506038659e-007

How accurate is this result?

Indeed a plot shows that the cancellation in tan(x)-x destroys the accuracy of the function, and thus the accuracy of the zero.

>plot2d(&f(x)-1e-20,0.99*res1,1.01*res1,adaptive=0):

Interval Methods for Zeros

The function ibisect stops early.

>ibisect(&f(x),0,1,y=1e-20)

~3.091e-007,3.111e-007~

The Interval Newton Algorithm is not much better.

>mxminewton(&f(x),~1e-7,1e-6~,y=1e-20)

~3.1015e-007,3.1116e-007~

To get a better result, we need to approximate the function with its Taylor series, which can be evaluated very well.

>function f(x) &= taylor(tan(x),x,0,10)-x

                          9       7      5    3
                      62 x    17 x    2 x    x
                      ----- + ----- + ---- + --
                      2835     315     15    3

>mxminewton(&f(x),~1e-7,1e-6~,y=1e-20)

~3.1072325059538179e-007,3.10723250595382e-007~

Strictly, we have not solved tan(x)=x here. We need to add an error term to be precise. The error of the Taylor series is

 f^(11)(xi)/11! x^11

with some xi between 0 and x.

>function dtan11(x) &= diff(tan(x),x,11);

We add the error term to f.

>function fi(x) := f(x) + dtan11(0||~x~)/11!*x^11

Now we get an exact and guaranteed solution.

>ibisect("fi",1e-7,1e-6,y=1e-20)

~3.1072325059538174e-007,3.1072325059538211e-007~

Examples